With the proliferation of computer communication networks, such as IP network, telecommunication network, mobile ad-hoc network, and personal area network, many applications have been developed and deployed over said computer communication networks. These applications include healthcare system, e-prescription system, e-mail system, e-shopping system, e-auction system, multimedia system, pay-TV system, location based service system, and ubiquitous computing system etc. However, information, or more generically data, transferred through these systems is subject to hacking, snooping, eavesdropping, tampering, and manipulation and so on. While the degree of concern for security and privacy may vary from application to application and notably from person to person, it's a general requirement that digital information be securely delivered from the sender to the receiver, and that neither a third-party nor the receiver can jeopardize the information's security. In addition, it is required that the privacy of the sender, as well as the receiver, be preserved to a satisfactory extent.
An example for protecting the information's security is the secure e-mail system. In this case, only the sender and the receiver can interpret the e-mail. Another example is the secure electronic payment system, where only the owner of an account can spend the funds in the account.
Information privacy issues in many cases demand equal, if not heightened, awareness as information security issues. Consider the aforementioned secure e-mail and secure electronic payment systems, wherein the participants of e-mail and electronic payment systems expect that nobody else other than the participants knows the existence of communication. To protect the sender's privacy in an email, it may be necessary in some cases that even the receiver cannot tell who the sender is. For an electronic payment transaction, it may sometimes be preferable that the payee cannot identify the payer. There are many other examples for information privacy. When utilizing location based services, the location of the owner who carries a mobile device is in most cases under full control of the owner. In e-shopping, the payer may want to inhibit the online merchants from correlating her purchasing history, and then deducing her personal interest. In e-auction, the bidder may want to prevent competitors from analyzing her bidding strategy, and then using such knowledge to defeat her. Other examples include anonymous membership management and anonymous voter for e-voting etc.
In general, cryptographic communication systems are adapted to transfer a message between remote locations. Such systems include at least one encoding device at a first location and at least one decoding device at a second location, with the encoding and decoding devices both being coupled to computer communication networks. For digital systems, the message is defined to be a digital message, that is, a sequence of symbols from some alphabet. In practice, the alphabet is generally chosen to be the binary alphabet consisting of the symbols 0 and 1. In a typical communication session, each user's terminal is often equipped with both an encoder and a decoder so that the user can transmit and receive encrypted information to and from another user.
Conventionally, a number of public key cryptographic encoding and decoding techniques are readily available to provide some degree of security as well as privacy. For example, U.S. Pat. No. 4,405,829, issued to Rivest, et al., and El Gamal (Tahir ElGamal. A public-key cryptosystem and a signature scheme based on discrete logarithms. Advances in Cryptology Proceedings of CRYPTO 84, pages 10-18, 1985) are technologies well recognized in the field. The teaching of the Rivest patent and El Gamal is incorporated by reference.
In a public key cryptosystem, each user (e.g. user A) places in a public file an enciphering operator or public key, EA. User A keeps to himself the details of the corresponding deciphering operator or private key DA which satisfies the equationDA(EA(M))=M, for any message M. In order for the public key system to be practical, both EA and DA must be efficiently computable. However, user A must not compromise DA when revealing EA. That is, it should not be computationally feasible for an adversary to find an efficient way of computing DA, given only the enciphering key EA and probably some sorts of plain text-cipher text pairs. In a public key system, a judicious selection of keys ensures that only user A is able to compute DA efficiently.
Whenever another user (e.g. user B) wishes to send a message M to user A, he looks up EA in the public file and then sends the enciphered message EA (M) to user A. Upon receipt, user A deciphers the message by computingDA(EA(M))=M. Since DA is not derivable from EA in a practical way, only user A can decipher the message EA (M) sent to him. Similarly, if user A wants to send a message in response to user B, user A enciphers the response message using user B's encryption key EB, also available in the public file. Said procedure of secure communication implies that each user who wishes to receive private communication must place his enciphering key E in the public file. Or in other words, to securely communicate with other parties, with traditional public key cryptosystem such as RSA and El Gamal, user A is required to disclose his/her public key to outer world. However, in most cases, user A only possesses one public/private key pairs, i.e. one public key and its corresponding unique private key. This typical kind usage of public key cryptosystem has the unintentional consequence of making user A's public key properly serve as his/her identity. It means that even if a privacy concerned user is protected by such kinds of public key cryptosystem as well as other well designed privacy protection measures, an adversary is still capable of correlating activities of the user being protected through collecting and observing information released by the user based on the pattern of usage of the unique public key.
In the information age, privacy is broadly recognized as a dominant concern of information exchange. Privacy surveys show consistently that 80 to 90 percent of all people are concerned about privacy, and that 25 percent are willing to pay a considerable price in money or inconvenience for it. Such privacy protection significance not only exposes the shortcoming of the existing public key cryptosystem, but also emphasizes the importance and urgency of a new and improved anonymous public key methodology.
Within traditional public key cryptosystems, such as those disclosed by RSA and El Gamal, if user A is concerned that his/her single public key may violate his/her privacy, it's possible to eliminate the identifiable characteristics of the individual public key. The resort is no more than mandating concerned individual, say user A, to possess several distinct public keys and release each of the public keys to different correspondents with caution.
Besides possessing many public key pairs, Waters et al. have proposed a method making use of El Gamal cryptosystem to realize an Incomparable Public keys Scheme, by which a user can simultaneously possess several public keys while all these public keys correspond to a single private key. See B. R. Waters, E. W. Felten, A. Sahai, Receiver Anonymity via Incomparable Public keys, CCS'03, Washington, D.C., USA, pp. 112˜121. (hereinafter “Waters”). The teaching of Waters is also incorporated by reference.
By employing multiple public key pairs, conventional public key cryptosystems can mitigate the privacy concern to some extent. However, the concerned individual is still far from being satisfied. In fact, such measure has lots of drawbacks. For one, each distinct public key has a corresponding distinct private key which implies that along with the increasing number of public keys, the managing cost of public-private key pairs for individual increases. For two, each distinct public key has a corresponding distinct private key which implies that along with the increasing number of private keys, the security risk of loss or disclosure of private keys increases. For three, consider a person possessing 100 public key pairs which are definitely quite a lot for a person with traditional public key cryptosystems. Suppose the person intends to communicate with 200 correspondents either in parallel or serial communications. Consequently, at least every 2 out of the correspondents will sense the same public key of the privacy-concerned person, which is definitely considered as unacceptable privacy invasion. Finally, the receiver of a ciphered message may have to try all the private keys to decipher the message, which is very time consuming and inefficient.
Waters' scheme seems to be able to eliminate the managing cost of several public key pairs as well as concomitant security risks. However their Incomparable Public Keys Scheme generates new public keys by utilizing different generators to construct the public key of the El Gamal cryptosystem, which makes computation optimization difficult. For example, (g, ga) and (h, ha) are different public keys generated by Waters' Incomparable Public Keys Scheme, where g and h are different generators. Conventionally, the El Gamal cryptosystem makes use of only one generator hence it can be benefited by calculating the power of generator off-line and maintaining only one table of the power of generator. Waters' scheme requires either maintaining several tables of the power of different generators, or on-line computation, neither of which is very desirable in terms of computation optimization and cost management.